package com.hanxiaozhang.recursion.violentrecursion;

/**
 * 〈一句话功能简述〉<br>
 * 〈斐波那契数列〉
 *
 * @author hanxinghua
 * @create 2021/10/19
 * @since 1.0.0
 */
public class Fibonacci {

    public static void main(String[] args) {

        System.out.println(f(10));
        System.out.println(fDynamic(10));

    }


    public static int f(int n) {
        if (n == 1 || n == 2) {
            return 1;
        }
        return f(n - 1) + f(n - 2);
    }

    /**
     * 动态规划版本 ==> 记忆搜索
     *
     *
     * @param n
     * @return
     */
    public static int fDynamic(int n) {
        int[] cache = new int[n+1];
        cache[1] = 1;
        cache[2] = 1;
        for (int i = 3; i <= n; i++) {
            cache[i] = cache[i - 1] + cache[i - 2];
        }
        return cache[n];
    }

}
